//给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。 
//
// 假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。 
//
// 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,3,4,2,2]
//输出：2
// 
//
// 示例 2： 
//
// 
//输入：nums = [3,1,3,4,2]
//输出：3
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 10⁵ 
// nums.length == n + 1 
// 1 <= nums[i] <= n 
// nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次 
// 
//
// 
//
// 进阶： 
//
// 
// 如何证明 nums 中至少存在一个重复的数字? 
// 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？ 
// 
//
// Related Topics 位运算 数组 双指针 二分查找 👍 2239 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2023-09-20 10:23:06
 * @description 287.寻找重复数
 */
public class FindTheDuplicateNumber{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new FindTheDuplicateNumber().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	//鸽笼原理，每次交换把元素放入自己对应的桶，一定有一次交换不会成功，即是重复的元素
	public int findDuplicate1(int[] nums) {
		while (nums[0] != nums[nums[0]]) {
			int temp = nums[0];
			nums[0] = nums[nums[0]];
			nums[temp] = temp;
		}
		return nums[0];
	}
	/*二分查找，  onlogn
	* cnt[i]表示小于等于I的数有多少个，如果有重复的，则cnt[j]=j+1*/
	public int findDuplicate2(int[] nums) {
		int length = nums.length;
		int l=1,r=length-1,res=-1;
		while (l<=r){
			int m=(l+r)>>1;
			int cnt=0;
			for (int i = 0; i < length; i++) {
				if(nums[i]<=m) {
					cnt++;
				}
			}
			if(cnt<=m){
				l=m+1;
			}else {
				r=m-1;
				res=m;
			}
		}
		return res;
	}

	/*数字从1--n，则二进制展开后。
	统计每一位应该有的1的数量和实际的1的数量
	如果数量不同，说明当前位置有重复的数字，结果加上当前位置的|
	* 时间Onlogn  空间o1*/

		public int findDuplicate4(int[] nums) {
			int n = nums.length, ans = 0;
			int bit_max = 31;
			while (((n - 1) >> bit_max) == 0) {
				bit_max -= 1;
			}
			for (int bit = 0; bit <= bit_max; ++bit) {
				int x = 0, y = 0;
				for (int i = 0; i < n; ++i) {
					if ((nums[i] & (1 << bit)) != 0) {
						x += 1;
					}
					if (i >= 1 && ((i & (1 << bit)) != 0)) {
						y += 1;
					}
				}
				if (x > y) {
					ans |= 1 << bit;
				}
			}
			return ans;
		}


	/*快慢指针判圈
	* 快的走两步，慢的走一步，当快的和慢的第一次相遇时
	* 快的走了2(a+b）步，慢的走了a+b
	* 其中a是环的入口，b是入环后走的
	* 快的还可以表示成a+kl
	* 整理后，a=(k-1)l+L-b=(k-1)L+c
	* 其中相遇后再走c步到入口
	* 当第二次相遇时，即是入口
	* 时间On  空间01
	* */
	public int findDuplicate3(int[] nums) {
		int slow=0,fast=0;
		do{
			slow=nums[slow];
			fast=nums[nums[fast]];
		}while (slow!=fast);
		slow=0;
		//此时都走一步
		while (slow!=fast){
			slow=nums[slow];
			fast=nums[fast];
		}
		return slow;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
